Input buffered asynchronous transfer mode (ATM) or packet switch has worse switch performance than an output buffered switch since Head-Of-Line (HOL) blocking occurs in the input buffered ATM or packet switch. One of techniques that mitigate HOL blocking is a virtual output queuing (VOQ) of which each input port maintains a buffer for each output port. In VOQ, there are N input ports and each input port has N queues to the corresponding output ports. And then, in VOQ, there are N2 input queues in total. Transfer has to be made for just N queues among the N2 queues. Therefore, contention occurs among the input queues in VOQ. The well-known methods for achieving contention control include PIM (Parallel Iterative Matching), iSLIP, and 2DRR (Two-Dimensional Round-Robin) schemes.
PIM consists of 3 phases; request, grant and accept phases. In the request phase, each of N2 queues sends request to output ports. In the grant phase, each of the output ports grants one request among its own receiving requests using a random selection and notifies the result of grant to each of the input ports. An input port may receive several grants from each output port at the same time so that in the accept phase each of input port accepts one grant among its own receiving grants using a random selection. And several request-grant-accept phases are iteratively performed. In the PIM , although the performance of the PIM is enhanced with several request-grant-accept phases being iteratively made, it is difficult to achieve high-speed operation because of using random selection in the grant and accept phases.
The iSLIP has an architecture that discards the operation of the random selection of PIM and is described in U.S. Pat. No. 5,500,858, which is granted on Mar. 16, 1996, to N. McKeown, entitled “Method and apparatus for scheduling cells in an input queued switch” and the disclosure of which is incorporated herein by reference. The iSLIP uses a round-robin operation instead of a random selection in the grant and accept phases of the PIM. That is, in the iSLIP , one request among several requests and one grant among several grants are selected using round-robin pointers without using any random selection. However, in the iSLIP algorithm, as the number of input ports and output ports increases, the number of requests and accepts which must be searched in the grant and accept phases within one unit time also increases. As the result, it is difficult to achieve high-speed operation as the number of input ports and output ports in the iSLIP increase.
2DRR algorithm is described in U.S. Pat. No. 5,299,190, which granted on Mar. 29, 1994 to R. O. LaMaire et al., entitled “Two-dimensional round-robin scheduling mechanism for switches with multiple input queues”, the disclosure of which is incorporated herein by reference. In the 2DRR algorithm, request is determined with searching a request matrix in just N steps, which is a two-dimensional N×N matrix representing N2 requests. In the U.S. Pat. No. 5,299,190, “basic 2DRR algorithm” searches request matrix in accordance with a searching sequence defined in a pattern sequence matrix and determines request to be transmitted. And “enhanced 2DRR algorithm” makes improvement of “fairness property” for specific traffic pattern.
In the above mentioned 2DRR algorithm, if the number of input ports and output ports is large, a large number of search steps are needed to perform the 2DRR algorithm so that high-speed operation is not easily made.
Meanwhile, if the number of input ports and output ports increases, the number of FIFO queues existing in one input buffer module also increases. The number of input buffer modules increases as well. And then during the contention control, required amount of information is increasing so that the hardware implementation is difficult to be achieved.
To solve the above drawbacks of hardware implementation and at the same time to improve switch performance, there is an enhanced architecture, that is, input and output buffered architecture. In the input and output buffered switch, input ports and output ports are grouped by several of input ports and output ports to reduce the number of input buffer modules and the number of FIFO queues in each input buffer modules so that hardware implementation is easily achieved. However, since, in the input and output buffered architecture, a large number of FIFO queues in each input buffer module are served at the same time, a large number of switching planes necessarily exist. In the above-mentioned PIM, iSLIP, and 2DRR algorithms, selection of multiple FIFO queues in one input buffer module is not available and then these algorithms are not applicable to the input and output buffered architecture.
Meanwhile, 2DRRMS as a cell scheduling algorithm for the input and output buffered architecture is described in M. S. Han et al, entitled “Fast scheduling algorithm for input and output buffered ATM switch with multiple switching planes” (Electronics Letters, Vol.35, No.23, pp.1999-2000, November 1999). 2DRRMS uses request matrix and searches pattern matrix. In 2DRRMS, request matrix is searched in accordance with a sequence as defined in search pattern matrix and a request to be transmitted is determined. In the 2DRRMS method, assume that the size of group of input ports and output ports is k, and then m(=N/k) search steps are needed. According to the 2DRRMS method, operation speed k times higher than 2DRR algorithm which requires N search step may be achieved. However, in the case that N is relatively larger than k, a high-speed operation is not easily achieved.